package com.chj.chuji.tijie04;

import java.util.ArrayList;

public class IntervalTet {
	public static class Interval {
		int start;
		int end;

		Interval() {
			start = 0;
			end = 0;
		}

		Interval(int s, int e) {
			start = s;
			end = e;
		}
	}

	public static ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
		ArrayList<Interval> res = new ArrayList<>();
		if (intervals == null || newInterval == null) {
			return res;
		}
		// int index = 0;
		int i = 0;
		int ns = newInterval.start;// 插入新区间的起始点
		int ne = newInterval.end;// 插入新区间的终止点
		for (; i < intervals.size(); ++i) {
			if (intervals.get(i).start > ne) {
				// 如果ne比老区间的起始点都小那么可以直接退出
				// index = i;
				break;
			} else if (intervals.get(i).end < ns) {
				// 如果ns比老区间的终点都要大，那么把当前的区间加入res
				res.add(intervals.get(i));
			} else {
				// 如果ns比老区间的起点大但是比老区间的终点小，那么需要重新更新。
				ns = Math.min(ns, intervals.get(i).start);
				ne = Math.max(ne, intervals.get(i).end);

			}
		}
		res.add(new Interval(ns, ne));
		for (; i < intervals.size(); ++i) {
			res.add(intervals.get(i));
		}
		return res;
	}

	public static void main(String[] args) {
		ArrayList<Interval> intervals = new ArrayList<Interval>();
		Interval in01 = new Interval(1, 2);
		Interval in02 = new Interval(3, 5);
		Interval in03 = new Interval(6, 7);
		Interval in04 = new Interval(8, 10);
		Interval in05 = new Interval(12, 16);
		intervals.add(in01);
		intervals.add(in02);
		intervals.add(in03);
		intervals.add(in04);
		intervals.add(in05);

		Interval in06 = new Interval(4, 9);
		ArrayList<Interval> res = insert(intervals, in06);
		for (int i = 0; i < res.size(); i++) {
			Interval in = res.get(i);
			System.out.println(in.start + ", " + in.end);
		}
	}
}
